% tkz-tools-intersections.tex
% Copyright 2020  Alain Matthes
% This work may be distributed and/or modified under the
% conditions of the LaTeX Project Public License, either version 1.3
% of this license or (at your option) any later version.
% The latest version of this license is in
%   http://www.latex-project.org/lppl.txt
% and version 1.3 or later is part of all distributions of LaTeX
% version 2005/12/01 or later.
%
% This work has the LPPL maintenance status “maintained”.
%
% The Current Maintainer of this work is Alain Matthes.
%  utf8 encoding
\def\fileversion{3.06c}
\def\filedate{2020/04/06}
\typeout{2020/04/06 3.06c tkz-tools-intersections.tex}
\makeatletter
%<--------------------------------------------------------------------------–>
%                 intersection  de deux lignes
%<--------------------------------------------------------------------------–>
\def\tkzInterLL(#1,#2)(#3,#4){% méthode avec xfp
\tkz@InterLL(#1,#2)(#3,#4){tkzPointResult}
}

\def\tkz@InterLL(#1,#2)(#3,#4)#5{%
%\path (intersection of #1--#2 and #3--#4) coordinate(#5);
% méthode with tikz
\pgfextractx{\pgf@x}{\pgfpointanchor{#1}{center}}%
\pgfextracty{\pgf@y}{\pgfpointanchor{#1}{center}}%
\tkz@ax\pgf@x%
\tkz@ay\pgf@y%
\pgfextractx{\pgf@x}{\pgfpointanchor{#2}{center}}%
\pgfextracty{\pgf@y}{\pgfpointanchor{#2}{center}}
\tkz@bx\pgf@x%
\tkz@by\pgf@y%
\pgfextractx{\pgf@x}{\pgfpointanchor{#3}{center}}%
\pgfextracty{\pgf@y}{\pgfpointanchor{#3}{center}}%
\tkz@cx\pgf@x%
\tkz@cy\pgf@y%
\pgfextractx{\pgf@x}{\pgfpointanchor{#4}{center}}%
\pgfextracty{\pgf@y}{\pgfpointanchor{#4}{center}}%
\tkz@dx\pgf@x%
\tkz@dy\pgf@y%

\edef\tkz@deltax{\fpeval{(\tkz@ax-\tkz@bx)/(28.45274)}}
\edef\tkz@deltaxx{\fpeval{(\tkz@cx-\tkz@dx)/(28.45274)}}
\edef\tkz@deltay{\fpeval{(\tkz@ay-\tkz@by)/(28.45274)}}
\edef\tkz@deltayy{\fpeval{(\tkz@cy-\tkz@dy)/(28.45274)}}
\edef\tkz@deltaxy{\fpeval{((\tkz@ax*\tkz@by)-(\tkz@ay*\tkz@bx))/(28.45274*28.45274)}}
\edef\tkz@deltaxxyy{\fpeval{((\tkz@cx*\tkz@dy)-(\tkz@cy*\tkz@dx))/(28.45274*28.45274)}}
\edef\tkz@div{\fpeval{(\tkz@deltax*\tkz@deltayy)-(\tkz@deltay*\tkz@deltaxx)}}
\edef\tkz@numx{\fpeval{(\tkz@deltaxy*\tkz@deltaxx)-(\tkz@deltax*\tkz@deltaxxyy)}}
\edef\tkz@numy{\fpeval{(\tkz@deltaxy*\tkz@deltayy)-(\tkz@deltay*\tkz@deltaxxyy)}}
\edef\tkz@xs{\fpeval{round(\tkz@numx/\tkz@div,5)}}
\edef\tkz@ys{\fpeval{round(\tkz@numy/\tkz@div,5)}}
\path[coordinate](\tkz@xs,\tkz@ys) coordinate (#5);
}


% méthode with coordinates
\def\tkzInterLLxy(#1,#2,#3,#4)(#5,#6,#7,#8){%
%\path (intersection of #1--#2 and #3--#4) coordinate(#5);%
\tkz@ax#1%
\tkz@ay#2%
\tkz@bx#3%
\tkz@by#4%
\tkz@cx#5%
\tkz@cy#6%
\tkz@dx#7%
\tkz@dy#8%
\edef\tkz@deltax{\fpeval{(\tkz@ax-\tkz@bx)/(28.45274)}}
\edef\tkz@deltaxx{\fpeval{(\tkz@cx-\tkz@dx)/(28.45274)}}
\edef\tkz@deltay{\fpeval{(\tkz@ay-\tkz@by)/(28.45274)}}
\edef\tkz@deltayy{\fpeval{(\tkz@cy-\tkz@dy)/(28.45274)}}
\edef\tkz@deltaxy{\fpeval{((\tkz@ax*\tkz@by)-(\tkz@ay*\tkz@bx))/(28.45274*28.45274)}}
\edef\tkz@deltaxxyy{\fpeval{((\tkz@cx*\tkz@dy)-(\tkz@cy*\tkz@dx))/(28.45274*28.45274)}}
\edef\tkz@div{\fpeval{(\tkz@deltax*\tkz@deltayy)-(\tkz@deltay*\tkz@deltaxx)}}
\edef\tkz@numx{\fpeval{(\tkz@deltaxy*\tkz@deltaxx)-(\tkz@deltax*\tkz@deltaxxyy)}}
\edef\tkz@numy{\fpeval{(\tkz@deltaxy*\tkz@deltayy)-(\tkz@deltay*\tkz@deltaxxyy)}}
\edef\tkz@xs{\fpeval{round(\tkz@numx/\tkz@div,5)}}
\edef\tkz@ys{\fpeval{round(\tkz@numy/\tkz@div,5)}}
\path[coordinate](\tkz@xs,\tkz@ys) coordinate (tkzPointResult);
}

%<--------------------------------------------------------------------------–>
%                 intersection  de Ligne Cercle rayon connu
%<--------------------------------------------------------------------------–>
% /*
%    Calculate the intersection of a ray and a sphere
%    The line segment is defined from p1 to p2
%    The sphere is of radius r and centered at sc
%    There are potentially two points of intersection given by
%    p = p1 + mu1 (p2 - p1)
%    p = p1 + mu2 (p2 - p1)
%    Return FALSE if the ray doesn't intersect the sphere.
% */
% int RaySphere(XYZ p1,XYZ p2,XYZ sc,double r,double *mu1,double *mu2)
% {
%    double a,b,c;
%    double bb4ac;
%    XYZ dp;
%
%    dp.x = p2.x - p1.x;
%    dp.y = p2.y - p1.y;
%    dp.z = p2.z - p1.z;
%    a = dp.x * dp.x + dp.y * dp.y + dp.z * dp.z;
%    b = 2 * (dp.x * (p1.x - sc.x) + dp.y * (p1.y - sc.y) + dp.z * (p1.z - sc.z));
%    c = sc.x * sc.x + sc.y * sc.y + sc.z * sc.z;
%    c += p1.x * p1.x + p1.y * p1.y + p1.z * p1.z;
%    c -= 2 * (sc.x * p1.x + sc.y * p1.y + sc.z * p1.z);
%    c -= r * r;
%    bb4ac = b * b - 4 * a * c;
%    if (ABS(a) < EPS || bb4ac < 0) {
%       *mu1 = 0;
%       *mu2 = 0;
%       return(FALSE);
%    }
%
%    *mu1 = (-b + sqrt(bb4ac)) / (2 * a);
%    *mu2 = (-b - sqrt(bb4ac)) / (2 * a);
%
%    return(TRUE);
% }
%<---------- test ------------------------------------------------------–>
\def\tkzTestInterLC(#1,#2)(#3,#4){%
\tkz@Projection(#1,#2)(#3){tkz@pth}% distance centre à la ligne
\tkz@@CalcLength(#3,tkz@pth){tkz@mathLen}%
\tkzCalcLength(#3,#4)
\ifdim\tkz@mathLen pt>\tkzLengthResult pt\relax%
\def\tkzflagLC{-1}
\else
\def\tkzflagLC{1}
\fi
}
%<--------------------------------------------------------------------------–>
\def\tkz@numlc{0}
\pgfkeys{/linecircle/.cd,
 	node/.code           = \def\tkz@numlc{0},
 	R/.code             	= \def\tkz@numlc{1},
  with nodes/.code    	= \def\tkz@numlc{2},
	node
 }
%<--------------------------------------------------------------------------–>
\def\tkzInterLC{\pgfutil@ifnextchar[{\tkz@InterLC}{\tkz@InterLC[]}}
\def\tkz@InterLC[#1](#2,#3)(#4,#5){%
\begingroup
\pgfqkeys{/linecircle}{#1}
 \pgfinterruptboundingbox
\ifcase\tkz@numlc%
 		% first case 0
	\tkzCalcLength(#4,#5)
	\tkzInterLCR(#2,#3)(#4,\tkzLengthResult pt){tkzFirstPointResult}%
											   {tkzSecondPointResult}
\or% 1
    \tkzInterLCR(#2,#3)(#4,#5){tkzFirstPointResult}
    						   {tkzSecondPointResult}%
\or% 2
    \tkzInterLCWithNodes(#2,#3)(#4,#5){tkzFirstPointResult}%
    						    	  {tkzSecondPointResult}%
\fi
\endpgfinterruptboundingbox
\endgroup
}
%<--------------------------------------------------------------------------–>
%<--------------------------------------------------------------------------–>
\def\tkzInterLCR(#1,#2)(#3,#4)#5#6{%
\begingroup
\tkz@radi=#4%
\tkz@@extractxy{#3}
\tkz@bx =\pgf@x\relax%
\tkz@by =\pgf@y\relax%
\tkz@Projection(#1,#2)(#3){tkz@pth}
\tkz@@CalcLength(#3,tkz@pth){tkz@mathLen}
 \ifdim\tkz@mathLen pt<0.05pt\relax%
        \pgfpointdiff{\pgfpointanchor{#1}{center}}%
                     {\pgfpointanchor{#2}{center}}%
        \tkz@ax=\pgf@x%
        \tkz@ay=\pgf@y%
        \pgfpointborderellipse{\pgfpoint{\tkz@ax}{\tkz@ay}}%
                              {\pgfpoint{\tkz@radi}{\tkz@radi}}
        \tkz@ax=\pgf@x\relax%
        \tkz@ay=\pgf@y\relax%
        \advance\tkz@bx by\tkz@ax\relax%
        \advance\tkz@by by\tkz@ay\relax%
	     \pgfcoordinate{#6}{\pgfqpoint{\tkz@bx}{\tkz@by}}
        \tkzCSym(#3)(#6){#5}
  \else
	     \edef\pgfmathresult{\fpeval{\tkz@mathLen/\tkz@radi}}
			% \edef\tkz@angle{\fpeval{acosd(\pgfmathresult)}}
        \pgfmathacos@{\pgfmathresult}%
        \let\tkz@angle\pgfmathresult%
        \pgfpointdiff{\pgfpointanchor{#3}{center}}%
                     {\pgfpointanchor{tkz@pth}{center}}%
        \tkz@ax=\pgf@x%
        \tkz@ay=\pgf@y%
        \pgfpointborderellipse{\pgfpoint{\tkz@ax}{\tkz@ay}}%
                              {\pgfpoint{\tkz@radi}{\tkz@radi}}
        \tkz@ax =\pgf@x\relax%
        \tkz@ay =\pgf@y\relax%
        \advance\tkz@bx by\tkz@ax\relax%
        \advance\tkz@by by\tkz@ay\relax%
        \tkz@@extractxy{#3}
        \tkz@ax =\pgf@x\relax%
        \tkz@ay =\pgf@y\relax%
        \tkz@@extractxy{tkz@pth}
        \pgfmathrotatepointaround{\pgfpoint{\tkz@bx}{\tkz@by}}%
                                 {\pgfpoint{\tkz@ax}{\tkz@ay}}%
                                 {\tkz@angle}
	       \pgfcoordinate{#5}{\pgfqpoint{\pgf@x}{\pgf@y}}
        \pgfmathrotatepointaround{\pgfpoint{\tkz@bx}{\tkz@by}}%
                                 {\pgfpoint{\tkz@ax}{\tkz@ay}}%
                                 {-\tkz@angle}
	\pgfcoordinate{#6}{\pgfqpoint{\pgf@x}{\pgf@y}}

\fi
\endgroup
}
%<--------------------------------------------------------------------------–>
%                 intersection  de Ligne Cercle
% #4 center #5 point sur le cercle
%<--------------------------------------------------------------------------–>
% \def\tkzInterLC(#1,#2)(#3,#4)#5#6{%
%     \begingroup
%     \tkzCalcLength(#3,#4)\tkzGetLength{tkz@rad}
%     \tkzInterLCR(#1,#2)(#3,\tkz@rad pt){#5}{#6}
% \endgroup
% }
%<--------------------------------------------------------------------------–>
%                 intersection  de Ligne Cercle rayon inconnu
%<--------------------------------------------------------------------------–>
\def\tkzInterLCWithNodes(#1,#2)(#3,#4,#5)#6#7{%
\begingroup
    \tkzCalcLength(#4,#5)\tkzGetLength{tkz@radius}
    \tkzInterLCR(#1,#2)(#3,\tkz@radius pt){#6}{#7}
\endgroup
}

%<--------------------------------------------------------------------------–>
%    Intersection de deux cercles
%<--------------------------------------------------------------------------–>
\def\tkz@numcc{0}
\pgfkeys{
/circlecircle/.cd,
 node/.code          = {\global\def\tkz@numcc{0}},
 R/.code             = {\global\def\tkz@numcc{1}},
with nodes/.code     = {\global\def\tkz@numcc{2}}
}
%<--------------------------------------------------------------------------–>
\def\tkzInterCC{\pgfutil@ifnextchar[{\tkz@InterCC}{\tkz@InterCC[]}}
\def\tkz@InterCC[#1](#2,#3)(#4,#5){%
\begingroup
\pgfkeys{/circlecircle/.cd,node}
\pgfqkeys{/circlecircle}{#1}
\ifcase\tkz@numcc%
 % first case 0
  \tkz@save@length
  \tkzCalcLength(#2,#3)	\tkzGetLength{tkz@rayA}
  \tkzCalcLength(#4,#5) \tkzGetLength{tkz@rayB}
  \tkz@restore@length
  \tkzInterCCR(#2,\tkz@rayA pt)(#4,\tkz@rayB pt){tkzFirstPointResult}{%
                                                 tkzSecondPointResult}
  \or% 1
 \tkzInterCCR(#2,#3)(#4,#5){tkzFirstPointResult}{tkzSecondPointResult}%
  \or%2
 \tkzInterCCWithNodes(#2,#3)(#4,#5){tkzFirstPointResult}{tkzSecondPointResult}
\fi
\endgroup
}
%<--------------------------------------------------------------------------–>
%<--------------------------------------------------------------------------–>

% méthode
% /* circle_circle_intersection() *
%  * Determine the points where 2 circles in a common plane intersect.
%  *
%  * int circle_circle_intersection(
%  *                                // center and radius of 1st circle
%  *                                double x0, double y0, double r0,
%  *                                // center and radius of 2nd circle
%  *                                double x1, double y1, double r1,
%  *                                // 1st intersection point
%  *                                // 2nd intersection point
%  *
%  * This is a public domain work. 3/26/2005 Tim Voght
%  *
% int circle_circle_intersection(double x0, double y0, double r0,
%                                double x1, double y1, double r1,
%                                double *xi, double *yi,
%                                double *xi_prime, double *yi_prime)
% {
%   double a, dx, dy, d, h, rx, ry;
%   double x2, y2;
%
%   /* dx and dy are the vertical and horizontal distances between
%    * the circle centers.
%    */
%   dx = x1 - x0;
%   dy = y1 - y0;
%
%   /* Determine the straight-line distance between the centers. */
%   //d = sqrt((dy*dy) + (dx*dx));
%   d = hypot(dx,dy); // Suggested by Keith Briggs
%
%   /* Check for solvability. */
%   if (d > (r0 + r1))
%   {
%     /* no solution. circles do not intersect. */
%     return 0;
%   }
%   if (d < fabs(r0 - r1))
%   {
%     /* no solution. one circle is contained in the other */
%     return 0;
%   }
%
%   /* 'point 2' is the point where the line through the circle
%    * intersection points crosses the line between the circle
%    * centers.
%    */
%
%   /* Determine the distance from point 0 to point 2. */
%   a = ((r0*r0) - (r1*r1) + (d*d)) / (2.0 * d) ;
%
%   /* Determine the coordinates of point 2. */
%   x2 = x0 + (dx * a/d);
%   y2 = y0 + (dy * a/d);
%
%   /* Determine the distance from point 2 to either of the
%    * intersection points.
%    */
%   h = sqrt((r0*r0) - (a*a));
%
%   /* Now determine the offsets of the intersection points from
%    * point 2.
%    */
%   rx = -dy * (h/d);
%   ry = dx * (h/d);
%
%   /* Determine the absolute intersection points. */
%   *xi = x2 + rx;
%   *xi_prime = x2 - rx;
%   *yi = y2 + ry;
%   *yi_prime = y2 - ry;
%
%   return 1;
% }

\def\tkzInterCCR(#1,#2)(#3,#4)#5#6{%
\begingroup
\pgfinterruptboundingbox
\tkz@save@length
\tkzCalcLength(#1,#3)\tkzGetLength{tkz@dd}
\tkz@restore@length
\pgfextractx{\pgf@x}{\pgfpointanchor{#1}{center}}
\pgfextracty{\pgf@y}{\pgfpointanchor{#1}{center}}
\tkz@ax\pgf@x %
\tkz@ay\pgf@y %
\pgfextractx{\pgf@x}{\pgfpointanchor{#3}{center}}
\pgfextracty{\pgf@y}{\pgfpointanchor{#3}{center}}
\tkz@bx\pgf@x %
\tkz@by\pgf@y %
\tkz@cx#2 %
\tkz@cy#4 %
\edef\tkz@aa{\fpeval{((\tkz@cx+\tkz@cy)/(2*\tkz@dd))*(\tkz@cx-\tkz@cy)+\tkz@dd/2}}
\edef\tkz@xx{\fpeval{\tkz@ax+\tkz@aa/\tkz@dd*(\tkz@bx - \tkz@ax)}}
\edef\tkz@yy{\fpeval{\tkz@ay+\tkz@aa/\tkz@dd*(\tkz@by - \tkz@ay)}}
\path[coordinate](\tkz@xx pt,\tkz@yy pt) coordinate (tkzRadialCenter);
\edef\tkz@hh{\fpeval{sqrt((\tkz@cx+\tkz@aa)*(\tkz@cx-\tkz@aa))}}
\edef\tkz@rx{\fpeval{\tkz@hh / \tkz@dd * (\tkz@ay - \tkz@by)}}
\edef\tkz@ry{\fpeval{\tkz@hh / \tkz@dd * (\tkz@bx - \tkz@ax)}}
\edef\tkz@xs{\fpeval{\tkz@xx + \tkz@rx}}
\edef\tkz@ys{\fpeval{\tkz@yy + \tkz@ry}}
\path[coordinate](\tkz@xs pt,\tkz@ys pt) coordinate (#5);
\edef\tkz@xss{\fpeval{\tkz@xx - \tkz@rx}}
\edef\tkz@yss{\fpeval{\tkz@yy - \tkz@ry}}
\path[coordinate](\tkz@xss pt,\tkz@yss pt) coordinate (#6);
\endpgfinterruptboundingbox
\endgroup
}
%<--------------------------------------------------------------------------–>
% #2 node #3 node #4 node #5 node
% \def\tkzInterCC(#1,#2)(#3,#4)#5#6{%
% \begingroup
%   \tkzCalcLength(#1,#2)\tkzGetLength{tkz@rayA}
%   \tkzCalcLength(#3,#4)\tkzGetLength{tkz@rayB}
%   \tkzInterCCR(#1,\tkz@rayA pt)(#3,\tkz@rayB pt){#5}{#6}
% \endgroup
% }
%<--------------------------------------------------------------------------–>
%    Intersection de deux cercles   Avec deux points
%<--------------------------------------------------------------------------–>
% la première variante devrait être #2 #3  avec #4 #5
\def\tkzInterCCWithNodes(#1,#2,#3)(#4,#5,#6)#7#8{%
\begingroup
  \tkzCalcLength(#2,#3)\tkzGetLength{tkz@rayA}
  \tkzCalcLength(#5,#6)\tkzGetLength{tkz@rayB}
  \tkzInterCCR(#1,\tkz@rayA pt)(#4,\tkz@rayB pt){#7}{#8}
\endgroup
}
\makeatother
\endinput
